//
//  Problem1351.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/4/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1351. 统计有序矩阵中的负数
 给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
 请你统计并返回 grid 中 负数 的数目。

 示例 1：
     输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
     输出：8
     解释：矩阵中共有 8 个负数。
 示例 2：
     输入：grid = [[3,2],[1,0]]
     输出：0
 示例 3：
     输入：grid = [[1,-1],[-1,-1]]
     输出：3
 示例 4：
     输入：grid = [[-1]]
     输出：1
 提示：
     m == grid.length
     n == grid[i].length
     1 <= m, n <= 100
    -100 <= grid[i][j] <= 100
 */
@objcMembers class Problem1351: NSObject {
    func solution() {
        print(countNegativesEr([[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]))
        print(countNegativesEr([[3,2],[1,0]]))
        print(countNegativesEr([[1,-1],[-1,-1]]))
        print(countNegativesEr([[-1]]))
    }
    
    /*
     暴力破解：
     优化：看看有从第几行开始是负数
     1: 查询最后一行，看看有从第几行开始是负数
     2: 遍历是负数的每一列(0~end) 第一个end是grid的长度， 然后查询这列的第一个是负数的位置，让end=j
     */
    func countNegatives(_ grid: [[Int]]) -> Int {
        var result = 0
        
        // 看看有从第几行开始是负数
        var colum = 0
        for i in 0..<grid[0].count {
            if grid.last![i] < 0 {
                colum = i
                break
            }
        }
        
        var end = grid.count-1
        for i in colum..<grid[0].count {
            for j in 0...end {
                if grid[j][i] < 0 {
                    result += grid.count - j
                    end = j
                    break
                }
            }
        }
        
        return result
    }
    
    /*
     二分查找：遍历每一行，迅速查找每一行的第一个负数的位置
     */
    func countNegativesEr(_ grid: [[Int]]) -> Int {
        var result = 0
        
        for row in grid {
            var l = 0
            var r = row.count-1
            var mid = 0
            var start = -1
            while l <= r {
                mid = l + (r - l) >> 1
                
                if row[mid] < 0 {
                    r = mid - 1
                    start = mid
                } else {
                    l = mid + 1
                }
            }
            if start != -1 {
                result += row.count - start
            }
        }
        
        return result
    }
}
